//
//  3_无重复字符的最长子串.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/7.
/**
 https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
 给定一个字符串 s ，请你找出其中不含有重复字符的 最长
 子串
  的长度。


 示例 1:

 输入: s = "abcabcbb"
 输出: 3
 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 
 示例 2:
 输入: s = "bbbbb"
 输出: 1
 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 
 示例 3:
 输入: s = "pwwkew"
 输出: 3
 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 */

import UIKit
// 第三季 第一个视频后半部分
class GetlengthOfLongest: NSObject {
    
    func QA() {
        print(lengthOfLongestSubstring("abcabcbb"))
        print(lengthOfLongestSubstring("bbbbb"))
        print(lengthOfLongestSubstring("pwwkew"))

    }
    
    func lengthOfLongestSubstring(_ s: String) -> Int {
        
        if s.count < 2 {
            return s.count
        }
        var dict: [Character: Int] = [:] // 每个字符上次出现的位置
        let chars = Array(s)
        
        var i = 1
        var maxLength = 1 //
        var li = 0 // 以 i-1 结尾的最长不重复子串的开始索引
        if let temp = chars.first {
            dict[temp] = 0
        }
        while i < chars.count {
            let char = chars[i]
            let pi = dict[char] ?? -1 // 当前字符上一次出现的位置
            if pi != -1 && li <= pi {
                li = pi + 1
            }
            dict[char] = i
            maxLength = max(maxLength, i - li + 1)
            i += 1
        }
        
        return maxLength
    }
}
